package shuati.jianxinhuyu;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author : LdLtd
 * @Date : 2024/4/13
 * @Description:给定一个r行c列的二维数组m表示一个棋盘地图，
 * 数组元素取值0或者1，
 * 1表示对于地图格子有炸弹，当点击时，
 * 如果有炸弹会爆炸，周围8个格子也会爆炸，
 * 问最少点击几次全部爆炸
 */
public class zhadan {
    /*
    * 找到一个策略来点击格子，使得所有的炸弹都被触发爆炸。
    * 这个问题可以用图的广度优先搜索（BFS）来解决。你可以从每个炸弹的位置开始进行BFS搜索，
    * 每一层都是周围的八个格子。然后记录每个格子被访问的次数，
    * 最后统计需要多少次点击才能触发所有的炸弹爆炸。*/
    public static void main(String[] args) {
//        int [][] ar=new int[][]{
//                {0, 1, 0, 0, 0},
//                {1, 0, 0, 1, 0},
//                {0, 1, 0, 0, 0},
//                {0, 0, 1, 0, 1},
//                {1, 0, 0, 0, 0}
//        };
        //2
//        int [][] ar=new int[][]{
//                { 1, 0, 0, 1},
//                { 0, 1, 1, 0},
//                { 0, 0, 1, 0},
//                { 1, 0, 0, 1}
//        };
        //3
        int [][] ar=new int[][]{
                { 1, 0, 1, 0},
                { 0, 0, 0, 1},
                { 0, 0, 1, 1},
                { 1, 0, 0, 1}
        };
        System.out.println(bfs(ar));
    }
    //定义8个方向
    public static int [] dx={-1,0,1,1,1,0,-1,-1};
    public static int [] dy={1,1,1,0,-1,-1,-1,0};
    public static int bfs(int [][] ar){
            int rows=ar.length;
            if(rows==0) return 0;
            int cols=ar[0].length;
            int res=0;
        Deque<int[]>q=new LinkedList<>();
        //所有炸弹入队
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (ar[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    //bfs  从当前位置开始炸
                    while (!q.isEmpty()){
                            int [] cur=q.poll();
                            int x=cur[0];
                            int y=cur[1];
                            //触发炸弹
                            ar[x][y]=0;
                            for (int u = 0; u < 8; u++) {
                                int nx=x+dx[u];
                                int ny=x+dy[u];
                                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && ar[nx][ny] == 1) {
                                    // 如果相邻格子有炸弹，入队列
                                    q.push(new int[]{nx, ny});

                                }
                            }

                    }
                    res++;
                }
            }
        }
        return res-1;
    }
}
